package com.example.leetcode.nk.NC140;


import java.util.Arrays;

//排序
public class Solution {

    public int[] MySort (int[] arr) {
        // write code here

        //快速排序
        sort(0, arr.length-1, arr);
        return arr;
    }

    public void sort(int start, int end, int[] arr) {
        if (start >= end) {
            return;
        }
        int volicated = arr[start];
        int l = start;
        int r = end;

        while(l < r) {
            while(l < r && volicated <= arr[r]) {
                r--;
            }
            while(l < r && volicated >= arr[l]) {
                l++;
            }
            swap(l, r, arr);
        }
        swap(start, l , arr);
        sort(start, l-1, arr);
        sort(l+1, end, arr);
    }

    public void swap(int left, int right, int[] arr) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
//    public int[] mergeSort(int[] arr) {
//        if (arr.length <= 1) {
//            return arr;
//        }
//        int middle = arr.length/2;
//        mergeSort(Arrays.copyOf(arr, ))
//        return arr;
//    }
}
